package com.lry.basic.algorithm.recursion;

import java.util.*;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/26
 */
//给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
//        例如，给出 n = 3，生成结果为：
//        [
//        "((()))",
//        "(()())",
//        "(())()",
//        "()(())",
//        "()()()"
//        ]
public class GenerateParenthesis {
    public static void main(String[] args) {
        List<String> list = generateParenthesis(4);
        for (String s:list) {
            System.out.println(s);
        }
        generateParenthesisDP(5);
    }

    public static List<String> generateParenthesis(int n) {
        List<String>res = new ArrayList();
        if(n<1){
            return res;
        }
        dfs("",n,n,res);
        return res;
    }

    private static void dfs(String nodeStr,int left,int right,List<String>res){
        if(left==0&&right==0){
            res.add(nodeStr);
        }

        if(left>0){
            dfs(nodeStr+"(",left-1,right,res);
        }

        if(right>0&&right>left){
            dfs(nodeStr+")",left,right-1,res);
        }
    }

    public static List<String> generateParenthesisBFS(int n) {
        List<String>res = new ArrayList();
        if(n<1){
            return res;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node("",n,n));

        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.left==0&&node.right==0){
                res.add(node.res);
            }
            if(node.left>0){
                queue.offer(new Node(node.res+"(",node.left-1,node.right));
            }
            if(node.right>0&&node.right>node.left){
                queue.offer(new Node(node.res+")",node.left,node.right-1));
            }
        }
        return res;
    }
    //dp[i] = "("+dp[j]+")"+dp[i-1-j]  0<=j<i
    //dp[i] = "("+dp[i-1]+“)” || dp[i-1]+“()” || "()"+dp[i-1]
    public static List<String> generateParenthesisDP(int n) {
        List<String>res = new ArrayList();
        if(n<1){
            return res;
        }
        //dp初始条件
        Map<Integer,List<String>>dp = new HashMap<>();
        dp.put(0,Arrays.asList(""));

        for(int i=1;i<=n;i++){
            List<String>list = new ArrayList<>();
            for(int j=0;j<i;j++){
                for(String s:dp.get(j)){
                    for(String s1:dp.get(i-1-j)){
                        list.add("("+s+")"+s1);
                    }
                }
            }
            dp.put(i,list);
        }

        return dp.get(n);
    }

    static class Node{
        public String res;//当前节点字符串 类似 "()()"
        public int left; //当前节点还剩余多少左括号
        public int right;//当前节点还剩余多少右括号
        public Node(String res,int left,int right){
            this.res = res;
            this.left = left;
            this.right = right;
        }
    }
}


